package com.ryujung.array.leetCode_1;

import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 思路：
     * 1.（暴力）使用双循环遍历数组，并判断指针处的两数之和
     * 是否符合条件，将符合条件的数放入结果集中
     * 注意：
     * 1.根据题目只需返回一个答案即可
     * 2.要防止数值溢出
     */
    public static int[] twoSum1(int[] nums, int target) {
        if (nums == null || nums.length < 2)
            return null;

        for (int i = 0; i < nums.length; i++) {
            for (int n = nums.length - 1; n > i; n--) {
                if (nums[i] + nums[n] == target) {
                    return new int[]{i, n};
                }
            }
        }
        return null;
    }
    // 时间复杂度为：O(n^2)
    // 空间复杂度为：O(1)

    /**
     * 思路：
     * 将nums中的每个数字,以及满足相加为target的对应 "被加数"，存入一个map中，
     * 同时判断当前被遍历的数，是否已经存在于map的"被加数"中，如果存在，
     * 直接返回结果即可
     * 总结：
     * 这是一种利用空间 换 计算时间 的方法
     */
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int v = target - nums[i];
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            // 将当前角标数字需要的被加数存入key，角标为值
            map.put(v, i);
        }
        return null;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)

}
//leetcode submit region end(Prohibit modification and deletion)
